package LeetCode刷题;

import java.util.HashSet;

/**
 * @program: Java_Study
 * @author: Xiaofan
 * @createTime: 2021-10-23 10:35
 * @description: Functions of this class is
 * 官方题解：(最优解法，马拉车解法)
 * class Solution {
 *     public String longestPalindrome(String s) {
 *         int start = 0, end = -1;
 *         StringBuffer t = new StringBuffer("#");
 *         for (int i = 0; i < s.length(); ++i) {
 *             t.append(s.charAt(i));
 *             t.append('#');
 *         }
 *         t.append('#');
 *         s = t.toString();
 *
 *         List<Integer> arm_len = new ArrayList<Integer>();
 *         int right = -1, j = -1;
 *         for (int i = 0; i < s.length(); ++i) {
 *             int cur_arm_len;
 *             if (right >= i) {
 *                 int i_sym = j * 2 - i;
 *                 int min_arm_len = Math.min(arm_len.get(i_sym), right - i);
 *                 cur_arm_len = expand(s, i - min_arm_len, i + min_arm_len);
 *             } else {
 *                 cur_arm_len = expand(s, i, i);
 *             }
 *             arm_len.add(cur_arm_len);
 *             if (i + cur_arm_len > right) {
 *                 j = i;
 *                 right = i + cur_arm_len;
 *             }
 *             if (cur_arm_len * 2 + 1 > end - start) {
 *                 start = i - cur_arm_len;
 *                 end = i + cur_arm_len;
 *             }
 *         }
 *
 *         StringBuffer ans = new StringBuffer();
 *         for (int i = start; i <= end; ++i) {
 *             if (s.charAt(i) != '#') {
 *                 ans.append(s.charAt(i));
 *             }
 *         }
 *         return ans.toString();
 *     }
 *
 *     public int expand(String s, int left, int right) {
 *         while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
 *             --left;
 *             ++right;
 *         }
 *         return (right - left - 2) / 2;
 *     }
 * }
 **/
public class NoNoNo动态规划最长回文子串 {
    public static void main(String args[]) {
        System.out.println(longestPalindrome("babad"));
    }
    public static String longestPalindrome(String s) {
        int len=s.length();
        if(len<2){//如果该字符串长度<2的话就必定为回文字符串，直接返回
            return s;
        }
        char c[]=s.toCharArray();
        boolean dp[][]=new boolean[len][len];//设定一个dp数组记录一个长度范围内是否为回文字符串
        int maxLen=1;//初始最长长度限定为1
        int begin=0;

        for(int i=0;i<len;i++){
            dp[i][i]=true;//字符串长度为1的肯定为回文字符串
        }
        for(int length=2;length<=len;++length){//先限定每次的回文子串的长度，从2开始

            for(int left=0;left<len;++left){//然后逐一枚举左边界
                //然后根据left和i的值，来限定右边界

                int right=left+length-1;
                System.out.println("fukc");
                if(right>=len){//说明右边界越界了，则直接退出
                    break;
                }
                if(c[left]!=c[right]){//如果当前字符不相等的话
                    dp[left][right]=false;
                }
                else{//如果相等的话 开始进行动态规划判断
                    if(right-left<3){//如果当前回文串长度小于3的话，则说明当前回文串是回文串
                        dp[left][right]=true;
                    }
                    else{//如果当前回文串长度大于2的话，则看下一个边界中的字符串是否是回文串
                        dp[left][right]=dp[left+1][right-1];
                    }
                }

                //判断完毕后，如果当前边界内的是回文串而长度比当前最长长度都要长的话，就记录一下开始点和长度
                if(dp[left][right]&&(right-left+1)>maxLen){
                    maxLen=right-left+1;
                    begin=left;
                }
            }
        }
        return s.substring(begin,begin+maxLen);
    }
}